import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int count=0;
        int cur=nums.length-1;
        int left=0;
        int right=cur-1;
        for(;cur>1;cur--){
            right=cur-1;
            left=0;

            while(left<right){

                if(nums[left]+nums[right]>nums[cur]){
                    count+=right-left;
                    right--;


                }else{
                    left++;
                }
            }

        }
        return count;
    }
}





class Solution1 {
    public List<List<Integer>> threeSum(int[] nums) {
        int size = nums.length;
        Arrays.sort(nums);

        List<List<Integer>> List = new ArrayList<>();

        for (int i = 0; i < size; i++) {

            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int tmp = nums[i];
            int size1 = size-1;
            for (int j = i + 1; j < size1; ) {

                if (j != i+1 && nums[j] == nums[j - 1]) {
                    j++;
                    continue;
                }

                int total = nums[j] + nums[size1];
                if (total == -tmp) {

                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[size1]);

                    List.add(list);
                    j++;
                    size1--;
                } else if (total > -tmp) {
                    size1--;
                }else{
                    j++;
                }
            }
        }
        return List;
    }

}








